package top.younote.learn.sort;

import java.io.IOException;

/**
 * @Description: 快速排序
 * @Author: duanyu
 * @CreateTime: 2020-08-23 16:59:54
 */
public class QuickSort {
    public static void main(String[] args) throws IOException {
        int[] sortNumsList = CommonUtils.readSortNums();
        int[] sortedNumsList = quickSort(sortNumsList, 0, sortNumsList.length-1);
        for (int cur : sortedNumsList) {
            System.out.println(cur);
        }
    }

    /**
     * 把第一个元素作为中心，将数组分成两部分，然后使用分治的思想，分而治之
     * @param sortNumsList
     * @param left
     * @param right
     * @return
     */
    private static int[] quickSort(int[] sortNumsList, int left, int right) {
        if (left < right) {
            int pivot = partition(sortNumsList, left, right);
            quickSort(sortNumsList, left, pivot - 1);
            quickSort(sortNumsList, pivot + 1, right);
        }
        return sortNumsList;
    }

    private static int partition(int[] part, int left, int right) {
        int pivot = part[left];
        while (left < right) {
            while (left < right && part[right] >= pivot) {
                right--;
            }
            part[left] = part[right];
            while (left < right && part[left] <= pivot) {
                left++;
            }
            part[right] = part[left];
        }
        part[left] = pivot;
        return left;
    }
}
